1. Field of the Invention
The present invention relates generally to systems and methods for producing digital signatures based on the hardness of solving a worst-case lattice problem
2. Description of the Related Art
Digital signatures are used for many applications, including verifying the identity of the sender of a message. Most digital signature schemes rely on the difficulty of factoring a large number obtained as a product of two large prime numbers, or on computing discrete logarithms.
Goldreich et al. proposed using lattice reduction problems as a basis for producing digital signatures in Advances in Cryptography—CRYPTO, Springer LNCS, 1294:112-131 (1997). A lattice is a collection of points in n-dimensional space which satisfy certain properties, including (1) zero is in the set; (2) if a, b are in the set, then a+b, a−b are also in the set; (3) the lattice is generated by at least one finite basis, i.e., there exists a finite set (called a “basis”) such that every point in the lattice is expressible as an integer linear combination of the elements in the basis. The “length” of a basis is the length of the longest vector in the basis. It happens that a lattice typically can be defined using one of many bases, with the shortest basis being hard to find when the number “n” of dimensions becomes large.
Accordingly, the present invention recognizes that in a lattice-based digital signature scheme, an n-dimensional lattice can be generated that has a hard-to-find short basis, which is used as a sender's private key to sign a message by mapping the message to a point in the n-dimensional space. A recipient of the message can access a public key—the lattice with a relatively long basis—to verify the sender's identity by verifying the location of the message in the n-dimensional space. Unfortunately, the scheme disclosed by Goldreich et al., as admitted by Goldreich et al., might result in mapping two messages close together in the n-dimensional space, which would defeat the scheme as to those two messages because both messages would have the same digital signature.
In the present assignee's U.S. Pat. No. 5,737,425 to Ajtai, incorporated herein by reference, an interactive message authentication system is disclosed which uses lattices. Although directed primarily to message authentication, the '425 patent discloses a method for deriving a lattice with a short basis. As recognized by the present invention, however, a digital signature system, unlike a message authentication system, must provide irrefutability of a signature, such that a recipient of a message can show a message to a third party to prove the identity of the signer of the message, a feature not generally required in message authentication systems. The requirement of irrefutability is particularly important in e-commerce applications. Moreover, the invention disclosed in Ajtai is interactive, which in the context of digital signatures could render it susceptible to so-called “intruder in the middle” attacks. With the above recognitions in mind, the present invention has provided the inventive solutions disclosed below.